{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Divide Two Integers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: divide"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数相除"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数，被除数&nbsp;<code>dividend</code>&nbsp;和除数&nbsp;<code>divisor</code>。将两数相除，要求 <strong>不使用</strong> 乘法、除法和取余运算。</p>\n",
    "\n",
    "<p>整数除法应该向零截断，也就是截去（<code>truncate</code>）其小数部分。例如，<code>8.345</code> 将被截断为 <code>8</code> ，<code>-2.7335</code> 将被截断至 <code>-2</code> 。</p>\n",
    "\n",
    "<p>返回被除数&nbsp;<code>dividend</code>&nbsp;除以除数&nbsp;<code>divisor</code>&nbsp;得到的 <strong>商</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>假设我们的环境只能存储 <strong>32 位</strong> 有符号整数，其数值范围是 <code>[−2<sup>31</sup>,&nbsp; 2<sup>31&nbsp;</sup>− 1]</code> 。本题中，如果商 <strong>严格大于</strong> <code>2<sup>31&nbsp;</sup>− 1</code> ，则返回 <code>2<sup>31&nbsp;</sup>− 1</code> ；如果商 <strong>严格小于</strong> <code>-2<sup>31</sup></code> ，则返回 <code>-2<sup>31</sup></code><sup> </sup>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> dividend = 10, divisor = 3\n",
    "<strong>输出:</strong> 3\n",
    "<strong>解释: </strong>10/3 = 3.33333.. ，向零截断后得到 3 。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> dividend = 7, divisor = -3\n",
    "<strong>输出:</strong> -2\n",
    "<strong>解释:</strong> 7/-3 = -2.33333.. ，向零截断后得到 -2 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= dividend, divisor &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li><code>divisor != 0</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [divide-two-integers](https://leetcode.cn/problems/divide-two-integers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [divide-two-integers](https://leetcode.cn/problems/divide-two-integers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['10\\n3', '7\\n-3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        c = Counter(nums)\n",
    "        for v in c.values():\n",
    "            if v % 2 != 0:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        lst=[0]*501\n",
    "        for i in range(len(nums)):\n",
    "            lst[nums[i]]+=1\n",
    "        for i in range(len(lst)):\n",
    "            if lst[i]%2==1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        num_count = Counter(nums)\n",
    "        for key, value in num_count.items():\n",
    "            if value % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        return all(v % 2 == 0 for v in Counter(nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i in dic:\n",
    "                dic[i] += 1\n",
    "            else:\n",
    "                dic[i] = 1\n",
    "        for j in dic:\n",
    "            if dic[j] & 1 :\n",
    "                return False\n",
    "           \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        num_count = {}\n",
    "        for ni in nums:\n",
    "            if ni not in num_count:\n",
    "                num_count[ni] = 0\n",
    "            num_count[ni] += 1\n",
    "        return all(freq%2==0 for freq in num_count.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        if len(nums)%2 != 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        for i in nums:\n",
    "            if nums.count(i)%2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        m = {}\n",
    "        for num in nums:\n",
    "            if num not in m.keys():\n",
    "                m[num] = 1\n",
    "            else:\n",
    "                m[num] += 1\n",
    "        for num, cnt in m.items():\n",
    "            if cnt % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        cnt=Counter(nums)\n",
    "        for c in cnt:\n",
    "            if cnt[c]%2==1:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dct = Counter(nums)     # counter计数器\n",
    "        return all(val % 2 == 0 for val in dct.values())   # 装有判断结果的生成器"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        freq = Counter(nums)   # 元素出现次数哈希表\n",
    "        return all(f % 2 == 0 for f in freq.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        mset = set()\n",
    "        for itm in nums:\n",
    "            if itm in mset:\n",
    "                mset.remove(itm)\n",
    "            else:\n",
    "                mset.add(itm)\n",
    "        return len(mset) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        counter = Counter(nums)\n",
    "        for v in counter.values():\n",
    "            if v % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        counter = Counter(nums)\n",
    "        for v in counter.values():\n",
    "            if v % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        dist = defaultdict(int)\n",
    "        for item in nums:\n",
    "            dist[item] +=1\n",
    "        for value in dist.values():\n",
    "            if value%2!=0:\n",
    "                return False\n",
    "        return True  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        return all(f % 2 == 0 for f in cnt.values())\n",
    "        # for k,v in cnt.items():\n",
    "        #     if v % 2:\n",
    "        #         return False\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        rec = {}\n",
    "        for num in nums:\n",
    "            if num in rec:\n",
    "                rec[num] += 1\n",
    "            else:\n",
    "                rec[num] = 1\n",
    "        for val in rec.values():\n",
    "            if val % 2 == 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % 2 != 0:\n",
    "            return False\n",
    "        dct = Counter(nums)     # counter计数器\n",
    "        return all(val % 2 == 0 for val in dct.values())   # 装有判断结果的生成器"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums) // 2\n",
    "        isSingle = [False] * 501\n",
    "        for num in nums:\n",
    "            isSingle[num] = not isSingle[num]\n",
    "        for flag in isSingle:\n",
    "            if flag:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        count = Counter(nums)\n",
    "        return all(value % 2 == 0 for value in count.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        d = self.count(nums)\n",
    "        for v in d.values():\n",
    "            if v & 1 == 1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def count(self, nums: List[int]) -> dict:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if num not in d.keys():\n",
    "                d[num] = 1\n",
    "            else:\n",
    "                d[num] += 1\n",
    "        return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        my_dic=collections.Counter(nums)\n",
    "        for i in my_dic.values():\n",
    "            if i%2==1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        ds = Counter(nums)\n",
    "        for _,v in ds.items():\n",
    "            if v % 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        freq = Counter(nums)   # 元素出现次数哈希表\n",
    "        return all(f % 2 == 0 for f in freq.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(0, len(nums) - 1, 2):\n",
    "            if nums[i] != nums[i + 1]:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        arr = [0] * 501\n",
    "        for i in nums:\n",
    "            arr[i] += 1\n",
    "\n",
    "        for i in arr:\n",
    "            if i & 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        ad={}\n",
    "        for i in nums:\n",
    "            ad[i]=ad.get(i,0)+1\n",
    "        r=[v for v in ad.values() if v%2==1]\n",
    "        if r:\n",
    "            return False\n",
    "        else:\n",
    "            return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        a = Counter(nums)\n",
    "        for v in a.values():\n",
    "            if v%2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        my_dic=collections.Counter(nums)\n",
    "        for i in my_dic.values():\n",
    "            if i%2==1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        c = Counter(nums)\n",
    "        return not any(v & 1 for v in c.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        return all(x%2==0 for x in Counter(nums).values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        dic = {}\n",
    "\n",
    "        for i in nums:\n",
    "            dic[i] = dic.get(i, 0) + 1\n",
    "        \n",
    "        for v in dic.values():\n",
    "            if v % 2 != 0:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        ans = collections.defaultdict(int)\n",
    "        for x in nums:\n",
    "            ans[x] += 1\n",
    "        for x in ans.values():\n",
    "            if x & 1:\n",
    "                return False\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n % 2 != 0:\n",
    "            return False\n",
    "        nums.sort()\n",
    "        for i in range(0,n,2):\n",
    "            if nums[i] != nums[i+1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        # 所有数字的个数都偶数\n",
    "        n = len(nums)\n",
    "        counter = collections.Counter(nums)\n",
    "        for k, v in counter.items():\n",
    "            if v % 2 == 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        for k, v in Counter(nums).items() :\n",
    "            if v % 2 :\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        for k,v in cnt.items():\n",
    "            if v % 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        for x in set(nums):\n",
    "            if nums.count(x) % 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        m = Counter(nums)\n",
    "        return all(m[k] % 2 == 0 for k in m)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        d = {}\n",
    "        for i in nums:\n",
    "            if not d.get(i, False):\n",
    "                d[i] = 1\n",
    "            else:\n",
    "                d[i] += 1\n",
    "        for k in d:\n",
    "            if d[k] % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        count=Counter(nums)\n",
    "        return all(c % 2 == 0 for c in count.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        n = len(nums) // 2\n",
    "        for i in range(n):\n",
    "            if nums[i * 2] != nums[i * 2 + 1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        d = {}\n",
    "        for num in nums:\n",
    "            if num in d:\n",
    "                d[num] += 1\n",
    "            else:\n",
    "                d[num] = 1\n",
    "        \n",
    "        for k,v in d.items():\n",
    "            if v % 2 == 1:\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        a = Counter(nums)\n",
    "        for j in a.values():\n",
    "            if j % 2 == 1:\n",
    "                return False\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        set1 = set(nums)\n",
    "        for i in set1:\n",
    "            count = nums.count(i)\n",
    "            if count % 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        for x in set(nums):\n",
    "            if nums.count(x) % 2 == 0:\n",
    "                pass\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        hashtable = dict()\n",
    "        res = 0\n",
    "        for i in nums:\n",
    "            if i not in hashtable:\n",
    "                hashtable[i] = 1\n",
    "            else:\n",
    "                hashtable[i] += 1\n",
    "        \n",
    "        for value in hashtable.values():\n",
    "            if value & 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def divideArray(self, nums: list[int]) -> bool:\n",
    "        freq = Counter(nums) #哈希表\n",
    "        return all(f % 2 == 0 for f in freq.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        fre = Counter(nums)\n",
    "        return all(f % 2==0 for f in fre.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        counter=Counter(nums)\n",
    "        if len(counter)>len(nums)/2:\n",
    "            return False\n",
    "        for v in counter.values():\n",
    "            if v%2!=0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        freq = Counter(nums)   # 元素出现次数哈希表\n",
    "        return all(f % 2 == 0 for f in freq.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        freq = Counter(nums)   # 元素出现次数哈希表\n",
    "        return all(f % 2 == 0 for f in freq.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        return all([x % 2 == 0 for x in Counter(nums).values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        d = dict()\n",
    "        for i in nums:\n",
    "            d[i] = d.get(i, 0) + 1\n",
    "        return all(not (i & 1) for i in d.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(1, len(nums), 2):\n",
    "            if nums[i] != nums[i - 1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def divideArray(self, nums: List[int]) -> bool:\r\n",
    "        records = {}\r\n",
    "        for num in nums:\r\n",
    "            records[num] = records.get(num, 0) + 1\r\n",
    "        \r\n",
    "        return all(x % 2 == 0 for x in records.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        from collections import Counter\n",
    "        cnt = Counter(nums)\n",
    "        for v in cnt.values():\n",
    "            if v%2 == 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        hh=[0]*501\n",
    "        a=0\n",
    "        for n in nums:\n",
    "            hh[n]+=1\n",
    "        for i in range(501):\n",
    "            if hh[i]%2==0:\n",
    "                a+=0\n",
    "            else:\n",
    "                a+=1\n",
    "        if a==0:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        return all(v % 2 == 0 for v in cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        d = Counter(nums)\n",
    "        for v in d.values():\n",
    "            if v%2!=0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        return not any([v%2 == 1 for v in Counter(nums).values()])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        count = [0] * 501\n",
    "        for num in nums:\n",
    "            count[num] += 1\n",
    "        for num in count:\n",
    "            if num % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        nums.sort()\n",
    "        for i in range(0,len(nums),2):\n",
    "            if nums[i] != nums[i+1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        freq = Counter(nums)\n",
    "        return all(f%2==0 for f in freq.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        num = list(set(nums))\n",
    "        for i in num:\n",
    "            if nums.count(i) % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        cnt = Counter(nums)\n",
    "        return all(va%2==0 for va in cnt.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        return sum(val % 2 > 0  for key,val in Counter(nums).items()) == 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        hash = [0]*501\n",
    "        for num in nums:\n",
    "            hash[num] += 1\n",
    "        for i in range(501):\n",
    "            if hash[i] % 2 == 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        freq = Counter(nums)   # 元素出现次数哈希表\n",
    "        return all(f % 2 == 0 for f in freq.values())\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        ans = [0] * 501\n",
    "        for x in nums:\n",
    "            ans[x] ^= 1\n",
    "        return sum(ans) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        # 使用Counter来计算nums中每个数字的频率\n",
    "        counts = Counter(nums)\n",
    "\n",
    "        # 遍历字典中的每个键值对\n",
    "        for num, freq in counts.items():\n",
    "            # 如果任何数字的计数不是偶数，返回False\n",
    "            if freq % 2 != 0:\n",
    "                return False\n",
    "\n",
    "        # 否则，返回True\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        fre = Counter(nums)\n",
    "        return all(f % 2==0 for f in fre.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        for i in nums:\n",
    "            if nums.count(i) % 2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        for i in range(0, n, 2):\n",
    "            if nums[i] != nums[i + 1]:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        return sum(val % 2 > 0  for key,val in Counter(nums).items()) == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        a=set(nums)\n",
    "        for num in a:\n",
    "            if nums.count(num)%2!=0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divideArray(self, nums: List[int]) -> bool:\n",
    "        s = set(nums)\n",
    "        for i in s:\n",
    "            if nums.count(i)%2 != 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximizeSweetness(self, sweetness: List[int], k: int) -> int:\n",
    "        # 二分法\n",
    "        # 很棒的解法：\n",
    "        # https://leetcode.cn/problems/divide-chocolate/solutions/1328110/by-jiong-jiong-jiong-jiong-z-p2wx/?envType=study-plan-v2&envId=baidu-2023-fall-sprint\n",
    "        def check_feasible(minSweet):\n",
    "            acc_sum = 0\n",
    "            count = 0\n",
    "            for i in range(len(sweetness)):\n",
    "                acc_sum += sweetness[i]\n",
    "                if acc_sum >= minSweet:\n",
    "                    acc_sum = 0\n",
    "                    count += 1\n",
    "            return count >= (k + 1)\n",
    "        \n",
    "        summ = sum(sweetness)\n",
    "        aveSweet = summ // (k + 1)\n",
    "        left = 0\n",
    "        right = aveSweet\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check_feasible(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 1. build adjacency list for undirected graph\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u-1].append(v-1)\n",
    "            g[v-1].append(u-1)\n",
    "        \n",
    "        # 2. build union find disjoint set for this graph\n",
    "        UF = UnionFind(n)\n",
    "        for u in range(n):\n",
    "            for v in g[u]:\n",
    "                UF.unionSet(u, v)\n",
    "        \n",
    "        # find root of disjoint set for each vertex in the graph\n",
    "        hashmap = defaultdict(list)         # key: root index, value: vertices in the disjoint set rooted at root\n",
    "        for u in range(n):\n",
    "            root = UF.findSet(u)\n",
    "            hashmap[root].append(u)\n",
    "        \n",
    "        # 3. for each disjoint set, if it isn't a bipartite, impossible to divide\n",
    "        ans = 0\n",
    "        for root, nodes in hashmap.items():\n",
    "            if not self.isBipartite(nodes, g):\n",
    "                return -1\n",
    "            else:\n",
    "                ans += self.bfs(nodes, g)\n",
    "        return ans \n",
    "\n",
    "    def bfs(self, nodes: List[int], graph: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        return max depth of disjoint set\n",
    "        nodes: all the vertices in the disjoint set\n",
    "        graph: adjacency list\n",
    "        \"\"\"\n",
    "        n = len(graph)\n",
    "        maxdepth = 0\n",
    "\n",
    "        for start in nodes:\n",
    "            depth = 0\n",
    "            queue = deque([start])\n",
    "            visited = [False] * n\n",
    "            visited[start] = True \n",
    "            while queue:\n",
    "                depth += 1 \n",
    "                for _ in range(len(queue)):\n",
    "                    u = queue.popleft()\n",
    "                    for v in graph[u]:\n",
    "                        if not visited[v]:\n",
    "                            queue.append(v)\n",
    "                            visited[v] = True \n",
    "            maxdepth = max(maxdepth, depth)\n",
    "        \n",
    "        return maxdepth\n",
    "\n",
    "\n",
    "    def isBipartite(self, nodes: List[int], graph: List[List[int]]) -> bool:\n",
    "        n = len(graph)\n",
    "        UF = UnionFind(n)\n",
    "        for i in nodes:\n",
    "            for j in range(len(graph[i])-1):\n",
    "                if UF.isSameSet(i, graph[i][j]):\n",
    "                    return False \n",
    "                else:\n",
    "                    UF.unionSet(graph[i][j], graph[i][j+1])\n",
    "        return True \n",
    " \n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))  \n",
    "        self.ranks = [0] * n            \n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "\n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "        \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      n = len(skill)\n",
    "      div, mod = divmod(sum(skill), (n // 2))\n",
    "      if mod:\n",
    "        return -1\n",
    "\n",
    "      if max(skill) >= div:\n",
    "        return -1\n",
    "      \n",
    "      mp = collections.defaultdict(int)\n",
    "\n",
    "      res = 0\n",
    "      for s in skill:\n",
    "        if div - s in mp:\n",
    "            res += s * (div - s)\n",
    "            mp[div - s] -= 1\n",
    "            if mp[div - s] == 0:\n",
    "              del mp[div - s]\n",
    "        else:\n",
    "            mp[s] += 1\n",
    "        \n",
    "      if len(mp):\n",
    "        return -1\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        s = sum(skill)\n",
    "        n = len(skill)\n",
    "        if s%(n//2)!=0:return -1\n",
    "        ss = s//(n//2)\n",
    "        ans = 0\n",
    "        cnt = Counter(skill)\n",
    "        for x in skill:\n",
    "            if x in cnt and cnt[x]>0:\n",
    "                y = ss - x\n",
    "                cnt[x]-=1\n",
    "\n",
    "                if y in cnt and cnt[y]>0:\n",
    "                    ans+=x*y\n",
    "                    cnt[y]-=1\n",
    "                else:\n",
    "                    return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      l, h = 1000, 0\n",
    "      n = len(skill)\n",
    "      s, m = 0, {}\n",
    "      d = set()\n",
    "      for x in skill:\n",
    "        s += x\n",
    "        d.add(x)\n",
    "        if x not in m:\n",
    "          m[x] = 1\n",
    "        else:\n",
    "          m[x] += 1\n",
    "        if x < l:\n",
    "          l = x\n",
    "        if x > h:\n",
    "          h = x\n",
    "      if n // 2 * (l + h) != s:\n",
    "        return -1\n",
    "      ans = 0\n",
    "      x = l\n",
    "      while x <= (l + h) // 2:\n",
    "        if x in d:\n",
    "          if x * 2 == (l + h):\n",
    "            if m[x] % 2 == 0:\n",
    "              ans += (x * x * (m[x] // 2))\n",
    "            else:\n",
    "              return -1\n",
    "          elif m[x] == m[l + h - x]:\n",
    "            ans += (x * (l + h - x) * m[x])\n",
    "          else:\n",
    "            return -1\n",
    "        x += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        sum=0\n",
    "        n=len(skill)\n",
    "        if n==2:\n",
    "            return skill[0]*skill[1]\n",
    "        t=skill[n//2-1]+skill[n//2]\n",
    "        for i in range(n//2):\n",
    "            if skill[i]+skill[n-i-1]!=t:\n",
    "                return -1\n",
    "            else:\n",
    "                sum+=skill[i]*skill[n-i-1]\n",
    "        return sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        lengh = len(skill)\n",
    "        if lengh == 2:\n",
    "            return skill[0] * skill[1]\n",
    "        else:\n",
    "            # 先排序。然后依次取头尾和。\n",
    "            # 如果从第二对开始不等于头尾和。则退出返回 -1\n",
    "            skill.sort()\n",
    "\n",
    "            tmp = skill[0] +skill[-1]\n",
    "            res = 0\n",
    "\n",
    "            for i in range(lengh // 2):\n",
    "                start = skill[i]\n",
    "                end = skill[-1 - i]\n",
    "                if start + end == tmp:\n",
    "                    res += start * end\n",
    "                else:\n",
    "                    return -1\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      skill.sort()\n",
    "\n",
    "      sum_ = skill[0] + skill[-1]\n",
    "\n",
    "      i = 1\n",
    "      j = len(skill) - 2\n",
    "\n",
    "      res = skill[0] * skill[-1]\n",
    "      while i < j:\n",
    "        if skill[i] + skill[j] != sum_:\n",
    "          return -1\n",
    "\n",
    "        res += skill[i] * skill[j]\n",
    "        i += 1\n",
    "        j -= 1\n",
    "      \n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total, m = sum(skill), len(skill) // 2\n",
    "        if total % m: return -1\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      total, m = sum(skill), len(skill) // 2\n",
    "      if total % m:\n",
    "        return -1\n",
    "      ans, s = 0, total // m\n",
    "      cnt = Counter(skill)\n",
    "      for x, c in cnt.items():\n",
    "        if c != cnt[s - x]:\n",
    "          return -1\n",
    "        ans += c * x * (s - x)\n",
    "      return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        count=(len(skill)+1)//2\n",
    "        skill_tep=sorted(skill)\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill_tep[i]+ skill_tep[len(skill)-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill_tep[i]*skill_tep[len(skill)-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        t = skill[0] + skill[-1]\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        r = len(skill) - 1\n",
    "        while l < r:\n",
    "            if t != skill[l] + skill[r]:\n",
    "                return -1\n",
    "            ans += skill[l] * skill[r]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        total = sum(skill)\n",
    "        cnt = n//2\n",
    "        target = total//cnt\n",
    "        ans = 0\n",
    "        record = Counter(skill)\n",
    "        for k in list(record.keys()):\n",
    "            if k >= target:\n",
    "                return -1\n",
    "            v = record[k]\n",
    "            if v == 0:\n",
    "                continue\n",
    "            t = target-k\n",
    "            if t == k:\n",
    "                if v&1:\n",
    "                    return -1\n",
    "                ans += k*k*(v//2)\n",
    "            else:\n",
    "                if record[t] < v:\n",
    "                    return -1\n",
    "                record[t] -= v\n",
    "                ans += k*t*v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      l, h = 1000, 0\n",
    "      n = len(skill)\n",
    "      s, m = 0, {}\n",
    "      for x in skill:\n",
    "        s += x\n",
    "        if x not in m:\n",
    "          m[x] = 1\n",
    "        else:\n",
    "          m[x] += 1\n",
    "        if x < l:\n",
    "          l = x\n",
    "        if x > h:\n",
    "          h = x\n",
    "      if n // 2 * (l + h) != s:\n",
    "        return -1\n",
    "      ans = 0\n",
    "      x = l\n",
    "      while x <= (l + h) // 2:\n",
    "        if x in m:\n",
    "          if x * 2 == (l + h):\n",
    "            if m[x] % 2 == 0:\n",
    "              ans += (x * x * (m[x] // 2))\n",
    "            else:\n",
    "              return -1\n",
    "          elif m[x] == m[l + h - x]:\n",
    "            ans += (x * (l + h - x) * m[x])\n",
    "          else:\n",
    "            return -1\n",
    "        x += 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        target = skill[0] + skill[-1]\n",
    "        ans = 0\n",
    "        for i in range(len(skill) >> 1):\n",
    "            if skill[i] + skill[-1-i] != target:\n",
    "                return -1\n",
    "            ans += skill[i] * skill[-1-i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      ans=0\n",
    "      d={}\n",
    "      tot=0\n",
    "      for i in skill:\n",
    "        tot+=i\n",
    "        if i in d:\n",
    "          d[i]+=1\n",
    "        else:\n",
    "          d[i]=1\n",
    "      s=2*tot//len(skill)\n",
    "      if 2*tot%(len(skill))!=0:\n",
    "        return -1\n",
    "      for i in d:\n",
    "        if not s-i in d or d[i]!=d[s-i]:\n",
    "          return -1\n",
    "        ans+=d[i]*i*(s-i)\n",
    "      return ans//2\n",
    "      \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total, m = sum(skill), len(skill) // 2\n",
    "        if total % m: return -1\n",
    "        ans, s = 0, total // m\n",
    "        cnt = Counter(skill)\n",
    "        for x, c in cnt.items():\n",
    "            if c != cnt[s - x]: return -1\n",
    "            ans += c * x * (s - x)\n",
    "        return ans // 2\n",
    "'''\n",
    "作者：灵茶山艾府\n",
    "链接：https://leetcode.cn/problems/divide-players-into-teams-of-equal-skill/solutions/2005108/pai-xu-hou-zui-xiao-zui-da-pi-pei-by-end-7sta/\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        n = len(skill)\n",
    "        left, right =0, n-1\n",
    "        ans = 0\n",
    "        temp_sum = sum(skill) // (n//2)\n",
    "\n",
    "        while left < right:\n",
    "            if skill[left] + skill[right] != temp_sum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans += skill[left] * skill[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        s = sum(skill)\n",
    "        teams = len(skill) // 2\n",
    "        if s % teams: return -1\n",
    "        cnt = Counter(skill)\n",
    "        total = s // teams\n",
    "        ans = 0\n",
    "        for a in cnt.keys():\n",
    "            if cnt[total - a] != cnt[a]:\n",
    "                return -1\n",
    "            ans += a * (total - a) * cnt[a]\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        sum = 0\n",
    "        n = len(skill)\n",
    "        if n == 2:return skill[0]*skill[1]\n",
    "        for i in range(1,n//2):\n",
    "            if skill[i] + skill[n-1-i] == skill[0]+skill[n-1]:\n",
    "                sum += (skill[i] * skill[n-1-i])\n",
    "            else:\n",
    "                return -1\n",
    "        return sum + (skill[0]*skill[n-1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        ans = 0\n",
    "        skill.sort()\n",
    "        left, right =0, len(skill) - 1\n",
    "        temp = skill[0] + skill[-1]\n",
    "        while left < right:\n",
    "            if skill[left] + skill[right] != temp:\n",
    "                return -1\n",
    "            ans += skill[left] * skill[right]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        # 排序+首尾配对\n",
    "        skill.sort()\n",
    "        sm = 0\n",
    "        n = len(skill)\n",
    "        res = 0\n",
    "        for i in range(n // 2):\n",
    "            cur_sm = skill[i] + skill[n - i - 1]\n",
    "            if sm == 0:\n",
    "                sm = cur_sm\n",
    "            elif sm != cur_sm:\n",
    "                return -1\n",
    "            res += skill[i] * skill[n - i - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans = 0\n",
    "        n = len(skill)\n",
    "        s = sum(skill) // (n // 2)\n",
    "        for i in range(n // 2):\n",
    "            if s != skill[i] + skill[n-i-1]:\n",
    "                # print(s, i, n-i-1)\n",
    "                return -1\n",
    "            ans += skill[i] * skill[n-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        res = 0\n",
    "        n = len(skill)\n",
    "        s = skill[0] + skill[-1]\n",
    "        for i in range(n // 2):\n",
    "            if skill[i] + skill[n - i - 1] != s:\n",
    "                return -1\n",
    "            res += skill[i] * skill[n - i - 1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        target = 2*sum(skill)//len(skill)\n",
    "       \n",
    "        if (2*sum(skill))%len(skill):\n",
    "            return -1\n",
    "        \n",
    "        res= {}\n",
    "        point = 0\n",
    "\n",
    "        for i in skill:\n",
    "            y=target-i\n",
    "            if y in res and res[y]:\n",
    "                res[y]-=1\n",
    "                point+=y*i\n",
    "            else:\n",
    "                if i in res:\n",
    "                    res[i]+=1\n",
    "                else:\n",
    "                    res[i]=1\n",
    "        \n",
    "        for k,v in res.items():\n",
    "            if v:\n",
    "                return -1\n",
    "        return point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        sort_skill = sorted(skill)\n",
    "        tmp = sort_skill[0] + sort_skill[-1]\n",
    "        n = len(skill)\n",
    "        out = 0\n",
    "        for i in range (n // 2):\n",
    "            a, b = sort_skill[i], sort_skill[n-i-1]\n",
    "            if a+b != tmp:\n",
    "                return -1\n",
    "            out += a * b\n",
    "        return out "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        p = 0\n",
    "        q = len(skill)-1\n",
    "        re = 0\n",
    "        su = skill[0] + skill[-1]\n",
    "        while p<q:\n",
    "            if skill[p] + skill[q] != su:\n",
    "                return -1\n",
    "            re += skill[p]*skill[q]\n",
    "            p += 1\n",
    "            q -= 1\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        i,j = 0, len(skill)-1\n",
    "        total = skill[i]+skill[j]\n",
    "        res = 0\n",
    "        while i<j:\n",
    "            if skill[i]+skill[j] == total:\n",
    "                res+=skill[i]*skill[j]\n",
    "                i+=1\n",
    "                j-=1\n",
    "                continue\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        count=int((len(skill)+1)/2)\n",
    "        skill_tep=sorted(skill)\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill_tep[i]+ skill_tep[len(skill)-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill_tep[i]*skill_tep[len(skill)-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\"\"\"\n",
    "1 2 3 3 4 5\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        skill.sort()\n",
    "\n",
    "        left = 0\n",
    "        right = n - 1\n",
    "        answer = 0\n",
    "        pre = skill[left] + skill[right]\n",
    "        while left < right:\n",
    "            s = skill[left] + skill[right]\n",
    "            if s == pre:\n",
    "                answer += skill[left] * skill[right]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans = 0\n",
    "        c = skill[0] + skill[-1]\n",
    "        n = len(skill)\n",
    "        for i in range(n>>1):\n",
    "            if skill[i] + skill[n-i-1] != c:\n",
    "                return -1\n",
    "            ans += skill[i] * skill[n-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total, m = sum(skill), len(skill) // 2\n",
    "        if total % m: return -1\n",
    "        ans, s = 0, total // m\n",
    "        cnt = Counter(skill)\n",
    "        for x, c in cnt.items():\n",
    "            if c != cnt[s - x]: return -1\n",
    "            ans += c * x * (s - x)\n",
    "        return ans // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        res=0\n",
    "        s=skill[0]+skill[-1]\n",
    "        for i in range(len(skill)//2):\n",
    "            x,y=skill[i],skill[-1-i]\n",
    "            if s!=x+y:\n",
    "                return -1\n",
    "            res+=x*y\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        sort_skill = sorted(skill)\n",
    "        tmp = sort_skill[0] + sort_skill[-1]\n",
    "        n = len(skill)\n",
    "        out = 0\n",
    "        for i in range (n // 2):\n",
    "            if sort_skill[i] + sort_skill[n-i-1] != tmp:\n",
    "                return -1\n",
    "            out += sort_skill[i] * sort_skill[n-i-1]\n",
    "        return out "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "      skill.sort()\n",
    "      n=len(skill)\n",
    "      ans=0\n",
    "      tot=skill[0]+skill[-1]\n",
    "      for i in range(n//2):\n",
    "        if skill[i]+skill[n-i-1]!=tot:\n",
    "          return -1\n",
    "        ans+=skill[i]*skill[n-i-1]\n",
    "      return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        total , m = sum(skill),len(skill)//2\n",
    "        if total % m : return -1 \n",
    "        ans , s = 0 , total //m\n",
    "        cnt = Counter(skill)\n",
    "        for x , c in cnt.items():\n",
    "            if c != cnt[s-x]:\n",
    "                return -1 \n",
    "            ans += c * x * (s-x)\n",
    "        return ans // 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        s=0\n",
    "        d=defaultdict(int)\n",
    "        for sk in skill:\n",
    "            s+=sk\n",
    "            d[sk]+=1\n",
    "        n=len(skill)>>1\n",
    "        if s%n!=0:\n",
    "            return -1\n",
    "        ans=0\n",
    "        s//=n\n",
    "        for sk in d.keys():\n",
    "            if d[s-sk]!=d[sk]:\n",
    "                return -1\n",
    "            ans+=d[sk]*sk*(s-sk)\n",
    "        return ans>>1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        leng=len(skill)\n",
    "        count=(leng+1)//2\n",
    "        skill.sort()\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill[i]+ skill[leng-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill[i]*skill[leng-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans = 0\n",
    "        cnt = skill[-1] + skill[0]\n",
    "        l, r = 0, len(skill) - 1\n",
    "        while l < r:\n",
    "            if skill[l] + skill[r] != cnt: return -1\n",
    "            ans += skill[l] * skill[r]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n=len(skill)\n",
    "        skill.sort()\n",
    "        target=skill[0]+skill[-1]\n",
    "        l,r=1,n-2\n",
    "        while l<r:\n",
    "            if skill[l]+skill[r]!=target:\n",
    "                return -1\n",
    "            l+=1\n",
    "            r-=1\n",
    "        ans=0\n",
    "        l,r=0,n-1\n",
    "        while l<r:\n",
    "            ans+=skill[l]*skill[r]\n",
    "            l+=1\n",
    "            r-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        sum = skill[0] + skill[-1]\n",
    "        ans = skill[0] * skill[-1]\n",
    "        for i in range(1, len(skill) // 2):\n",
    "            if skill[i] + skill[-i - 1] != sum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans += skill[i] * skill[-i - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        res=0\n",
    "        skill.sort()\n",
    "        score=skill[0]+skill[-1]\n",
    "        n=len(skill)\n",
    "        for i in range(len(skill)//2):\n",
    "            cur_score=skill[i]+skill[n-i-1]\n",
    "            if score!=cur_score:\n",
    "                return -1\n",
    "            res+=skill[i]*skill[n-i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        leng=len(skill)\n",
    "        count=(leng+1)//2\n",
    "        skill.sort()\n",
    "        skillnum=min(skill)+max(skill)\n",
    "        ans=0\n",
    "        for i in range(count):\n",
    "            if skill[i]+ skill[leng-1-i]!=skillnum:\n",
    "                return -1\n",
    "            else:\n",
    "                ans=ans+skill[i]*skill[leng-i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s: return -1\n",
    "            ans += x * y\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        left = 0\n",
    "        right = len(skill)-1\n",
    "        temp = skill[left]+skill[right]\n",
    "        res = 0\n",
    "        while left < right:\n",
    "            if skill[left]+skill[right]==temp:\n",
    "                res += skill[left]*skill[right]\n",
    "                left += 1\n",
    "                right -= 1\n",
    "            else:\n",
    "                return -1\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)//2\n",
    "        和 = sum(skill)\n",
    "        if 和%n:\n",
    "            return -1\n",
    "        和 //= n\n",
    "        字典 = dict()\n",
    "        for i in skill:\n",
    "            字典[i] = 字典.get(i, 0) + 1\n",
    "        if 和%2 == 0 and 和//2 in 字典:\n",
    "            if 字典[和//2] % 2 == 1:\n",
    "                return -1\n",
    "            else:\n",
    "                字典[和//2] //= 2\n",
    "        化学反应和 = 0\n",
    "        for i in 字典:\n",
    "            x = 和-i\n",
    "            if x not in 字典 or 字典[i] != 字典[x]:\n",
    "                return -1\n",
    "            化学反应和 += i*x*字典[i] \n",
    "            字典[x] = 0\n",
    "            字典[i] = 0\n",
    "        return 化学反应和"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        check = skill[0] + skill[-1]\n",
    "        ans = 0\n",
    "        \n",
    "\n",
    "        for i in range (len(skill)//2):\n",
    "            x,y = skill[i],skill[len(skill)-1-i]\n",
    "            if x + y != check:return -1\n",
    "            else:\n",
    "                ans += x *y\n",
    "            \n",
    "        return ans \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        total = sum(skill)\n",
    "        cnt = n//2\n",
    "        target = total//cnt\n",
    "        ans = 0\n",
    "        record = Counter(skill)\n",
    "        for k in record:\n",
    "            if k >= target:\n",
    "                return -1\n",
    "            v = record[k]\n",
    "            if v == 0:\n",
    "                continue\n",
    "            t = target-k\n",
    "            if t == k:\n",
    "                if v&1:\n",
    "                    return -1\n",
    "                ans += k*k*(v//2)\n",
    "            else:\n",
    "                if record[t] < v:\n",
    "                    return -1\n",
    "                record[t] -= v\n",
    "                ans += k*t*v\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        n = len(skill)\n",
    "        s = skill[-1]+skill[0]\n",
    "        if not all(skill[x]+skill[n-1-x]==s for x in range(n//2)):\n",
    "            return -1\n",
    "        ans = 0\n",
    "        for x in range(n//2):\n",
    "            ans += skill[x]*skill[n-1-x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        skill.sort()\n",
    "        ans, s = 0, skill[0] + skill[-1]\n",
    "        for i in range(len(skill) // 2):\n",
    "            x, y = skill[i], skill[-1 - i]\n",
    "            if x + y != s:\n",
    "                return -1\n",
    "            ans += x * y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        ans= 0 \n",
    "        sum_ = sum(skill)\n",
    "        n = len(skill)\n",
    "        group_sum = sum_*2 // n\n",
    "        counter = Counter(skill)\n",
    "        for k,v in counter.items() :\n",
    "            if v != counter[group_sum-k]:\n",
    "                return -1 \n",
    "            else :\n",
    "                ans += k * (group_sum-k)*v \n",
    "        return ans//2 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "\n",
    "        n = len(skill)\n",
    "        if n == 2:\n",
    "            return skill[0] * skill[1]\n",
    "\n",
    "        # 团队技能点之和\n",
    "        tn = sum(skill) * 2 / n\n",
    "\n",
    "        # 团队技能点之和是整数\n",
    "        if tn%1 != 0:\n",
    "            return -1\n",
    "\n",
    "        # 每一对的技能点\n",
    "        res = []\n",
    "        # 每一对出现的次数\n",
    "        rets = []\n",
    "        skill.sort()\n",
    "        # 总共出现的技能点数和次数\n",
    "        td = Counter(skill)\n",
    "        # 总共出现的技能点数\n",
    "        tl = list(td.keys())\n",
    "\n",
    "        def getResList(tl):\n",
    "            lent = len(tl)\n",
    "            # 技能点数列表为空，直接返回\n",
    "            if lent == 0:\n",
    "                return\n",
    "            # 技能点数列表为1个，判断这个数*2是否=团队的技能点之和\n",
    "            elif lent == 1:\n",
    "                # 等于团队的技能点之和，保存数值和次数\n",
    "                # 否则直接返回\n",
    "                if tl[0] * 2 == tn:\n",
    "                    res.append([tl[0], tl[0]])\n",
    "                    rets.append(td[tl[0]]/2)\n",
    "                    tl.pop()\n",
    "                    return\n",
    "                else:\n",
    "                    return\n",
    "\n",
    "            # 最大的数与最小的树开始遍历\n",
    "            # 最后一个数\n",
    "            r = tl[-1]\n",
    "            for i in range(lent-1):\n",
    "                # 和等于团队的技能点之和\n",
    "                if r + tl[i] == tn:\n",
    "                    # 数的个数是否相等\n",
    "                    if td[tl[i]] == td[r]:\n",
    "                        # 个数相等，保存数字\n",
    "                        res.append([tl[i], r])\n",
    "                        # 保存数字的个数\n",
    "                        rets.append(td[r])\n",
    "                        # 将数字去除，继续递归\n",
    "                        tl.pop(-1)\n",
    "                        tl.pop(i)\n",
    "                        # 继续递归\n",
    "                        getResList(tl)\n",
    "                        return\n",
    "            return\n",
    "        getResList(tl)\n",
    "        \n",
    "        if sum(rets) != n/2:\n",
    "            return -1\n",
    "        \n",
    "        return int(sum([res[i][0]*res[i][1]*rets[i] for i in range(len(rets))]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "\n",
    "        n = len(skill)\n",
    "        if n == 2:\n",
    "            return skill[0] * skill[1]\n",
    "\n",
    "        # 团队技能点之和\n",
    "        tn = sum(skill) * 2 / n\n",
    "\n",
    "        # 团队技能点之和是整数\n",
    "        if tn%1 != 0:\n",
    "            return -1\n",
    "\n",
    "        res = []\n",
    "        rets = []\n",
    "        skill.sort()\n",
    "        td = Counter(skill)\n",
    "        tl = list(td.keys())\n",
    "\n",
    "        def getResList(tl):\n",
    "            lent = len(tl)\n",
    "            if lent == 0:\n",
    "                return\n",
    "            elif lent == 1:\n",
    "                if tl[0] * 2 == tn:\n",
    "                    res.append([tl[0], tl[0]])\n",
    "                    rets.append(td[tl[0]]/2)\n",
    "                    tl.pop()\n",
    "                    return\n",
    "\n",
    "            # 最后一个数\n",
    "            r = tl[-1]\n",
    "            for i in range(lent-1):\n",
    "                # 和等于团队的技能点之和\n",
    "                if r + tl[i] == tn:\n",
    "                    # 数的个数是否相等\n",
    "                    if td[tl[i]] == td[r]:\n",
    "                        # 个数相等，保存数字\n",
    "                        res.append([tl[i], r])\n",
    "                        # 保存数字的个数\n",
    "                        rets.append(td[r])\n",
    "                        # 将数字去除，继续递归\n",
    "                        tl.pop(-1)\n",
    "                        tl.pop(i)\n",
    "                        # 继续递归\n",
    "                        getResList(tl)\n",
    "                        return\n",
    "            return\n",
    "        getResList(tl)\n",
    "        \n",
    "        if sum(rets) != n/2:\n",
    "            return -1\n",
    "        \n",
    "        return int(sum([res[i][0]*res[i][1]*rets[i] for i in range(len(rets))]))\n",
    "\n",
    "            \n",
    "\n",
    "        # def getResList(temp):\n",
    "        #     lt = len(temp)\n",
    "        #     if lt == 0:\n",
    "        #         return\n",
    "        #     # 最后一个数\n",
    "        #     r = temp[-1]\n",
    "        #     for i in range(lt - 1 ):\n",
    "        #         if temp[i] + r == tn:\n",
    "        #             res.append([temp[i], r])\n",
    "        #             temp.pop(-1)\n",
    "        #             temp.pop(i)\n",
    "        #             getResList(temp)\n",
    "        #             return\n",
    "        #     return\n",
    "        # getResList(t)\n",
    "        \n",
    "        # if len(res) != n/2:\n",
    "        #     return -1\n",
    "\n",
    "        # return sum(r[0]*r[1] for r in res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        l = collections.deque(sorted(skill))\n",
    "        target, res = sum(skill)*2//len(skill), 0\n",
    "        while l:\n",
    "            a, b = l.pop(), l.popleft()\n",
    "            if a+b==target: res+=a*b\n",
    "            else: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n=len(skill)\n",
    "        s,group=sum(skill)//(n//2),[[-1,-1]*(n//2)]\n",
    "        c=Counter(skill)\n",
    "        ret=0\n",
    "        print(c)\n",
    "        for k,v in c.items():\n",
    "            print(k,v)\n",
    "            if k+k==s:\n",
    "                ret+=(v//2)*(k*k)\n",
    "                continue\n",
    "            if c[s-k]>=v:\n",
    "                c[k]-=v\n",
    "                c[s-k]-=v\n",
    "                ret+=v*k*(s-k)\n",
    "            else:\n",
    "                return -1\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, a: List[int]) -> int:\n",
    "        n=len(a)\n",
    "        s=sum(a)\n",
    "        if s%(n//2)!=0:\n",
    "            return -1\n",
    "        s//=n//2\n",
    "        ans=0\n",
    "        from sortedcontainers import SortedList\n",
    "        u=SortedList(a)\n",
    "        for i in a:\n",
    "            if i not in u:\n",
    "                continue\n",
    "            u.remove(i)\n",
    "            if s-i not in u:\n",
    "                return -1\n",
    "            u.remove(s-i)\n",
    "            ans+=i*(s-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, S: List[int]) -> int:\n",
    "        A, B = sorted(S), sorted(S, reverse=True)\n",
    "        return sum(a * b for a, b in zip(A, B)) >> 1 if all(A[0] + B[0] == a + b for a, b in zip(A, B)) else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        n = len(skill)\n",
    "        m = n // 2\n",
    "        skill.sort()\n",
    "        arr = [None] * m\n",
    "        arr[0] = (skill[0], skill[-1], skill[0] * skill[-1])\n",
    "        l, r = 1, n - 2\n",
    "        index = skill[0] + skill[-1]\n",
    "        total = arr[0][-1]\n",
    "        flag = False\n",
    "        while l < r: \n",
    "            if skill[l] + skill[r] != index:\n",
    "                flag = True\n",
    "                break\n",
    "            arr[l] = (skill[l], skill[r], skill[l] * skill[r])\n",
    "            total += arr[l][-1]\n",
    "            l += 1\n",
    "            r -= 1\n",
    "        if flag: return -1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dividePlayers(self, skill: List[int]) -> int:\n",
    "        b=-1\n",
    "        skill.sort(reverse=False)\n",
    "\n",
    "        s = len(skill) / 2\n",
    "        # 获取数组长度 看看能分成几组\n",
    "\n",
    "        # 中位数相加\n",
    "        huaxue=skill[int(s)]+skill[int(s)-1]\n",
    "        # 得出化学反应\n",
    "\n",
    "        xc=[]\n",
    "        xin=[]\n",
    "        # xin拿来判断 是否和原本的列表一致 不一致给-1\n",
    "        for i in range(0,int(s)):\n",
    "            for j in range(len(skill)-i-1,len(skill)-i-2,-1):\n",
    "                if huaxue==skill[i]+skill[j]:\n",
    "                    xin.append(skill[i])\n",
    "                    xin.append(skill[j])\n",
    "                    xiangc=skill[i]*skill[j]\n",
    "                    xc.append(xiangc)\n",
    "\n",
    "        # 这是最终反应之和\n",
    "\n",
    "        # 排序一致 # xin拿来判断 是否和原本的列表一致 不一致给-1\n",
    "        xin.sort(reverse=False)\n",
    "        if xin==skill:\n",
    "            return sum(xc)\n",
    "        else:\n",
    "            return b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "\n",
    "        # Constants.\n",
    "        MAX_INT = 2147483647        # 2**31 - 1\n",
    "        MIN_INT = -2147483648       # -2**31\n",
    "        HALF_MIN_INT = -1073741824  # MIN_INT // 2\n",
    "\n",
    "        # Special case: overflow.\n",
    "        if dividend == MIN_INT and divisor == -1:\n",
    "            return MAX_INT\n",
    "\n",
    "        # We need to convert both numbers to negatives.\n",
    "        # Also, we count the number of negatives signs.\n",
    "        negatives = 2\n",
    "        if dividend > 0:\n",
    "            negatives -= 1\n",
    "            dividend = -dividend\n",
    "        if divisor > 0:\n",
    "            negatives -= 1\n",
    "            divisor = -divisor\n",
    "\n",
    "        doubles = []\n",
    "        powersOfTwo = []\n",
    "\n",
    "        # Nothing too exciting here, we're just making a list of doubles of 1 and\n",
    "        # the divisor. This is pretty much the same as Approach 2, except we're\n",
    "        # actually storing the values this time. */\n",
    "        powerOfTwo = 1\n",
    "        while divisor >= dividend:\n",
    "            doubles.append(divisor)\n",
    "            powersOfTwo.append(powerOfTwo)\n",
    "            # Prevent needless overflows from occurring...\n",
    "            if divisor < HALF_MIN_INT:\n",
    "                break\n",
    "            divisor += divisor # Double divisor\n",
    "            powerOfTwo += powerOfTwo\n",
    "\n",
    "        # Go from largest double to smallest, checking if the current double fits.\n",
    "        # into the remainder of the dividend.\n",
    "        quotient = 0\n",
    "        for i in reversed(range(len(doubles))):\n",
    "            if doubles[i] >= dividend:\n",
    "                # If it does fit, add the current powerOfTwo to the quotient.\n",
    "                quotient += powersOfTwo[i]\n",
    "                # Update dividend to take into account the bit we've now removed.\n",
    "                dividend -= doubles[i]\n",
    "\n",
    "        # If there was originally one negative sign, then\n",
    "        # the quotient remains negative. Otherwise, switch\n",
    "        # it to positive.\n",
    "        return quotient if negatives != 1 else -quotient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if abs(dividend) < abs(divisor):\n",
    "            return 0\n",
    "        if dividend == -2147483648 and divisor == -1:\n",
    "            return 2147483647\n",
    "        sign = True\n",
    "        if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):\n",
    "            sign = False\n",
    "        \n",
    "        up = abs(dividend)\n",
    "        down = abs(divisor)\n",
    "        res = 0\n",
    "        while up >= down:\n",
    "            tmp = down\n",
    "            r = 1\n",
    "            while tmp <= up:\n",
    "                tmp <<= 1\n",
    "                r <<= 1\n",
    "            tmp >>= 1\n",
    "            r >>= 1\n",
    "            up -= tmp\n",
    "            res += r\n",
    "        \n",
    "        if sign:\n",
    "            return res\n",
    "        else:\n",
    "            return -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return self.way2(dividend, divisor)\n",
    "    def way1(self,dividend,divisor):\n",
    "        if divisor == 0:\n",
    "            return -1\n",
    "        neg = (dividend < 0) != (divisor < 0)\n",
    "        dividend, divisor = abs(dividend), abs(divisor)\n",
    "        dividend_, divisor_ = dividend, divisor\n",
    "        ans, record = 0, 1\n",
    "        while dividend_ >= divisor:\n",
    "            dividend_ -= divisor_\n",
    "            divisor_ += divisor_\n",
    "            ans += record\n",
    "            record += record\n",
    "            if dividend_ < divisor_:\n",
    "                divisor_ = divisor#divisor_重置\n",
    "                record = 1 #如果能进入下一次，而且此时dividend_已经小于divisor_，说明上一轮的record加多了，应该重置\n",
    "        if neg:\n",
    "            ans = -ans\n",
    "        if ans < pow(-2,31) or ans > pow(2,31)-1:\n",
    "            return pow(2,31)-1\n",
    "        return ans\n",
    "    def way2(self,dividend,divisor):#recursive\n",
    "        def way2_helper(dividend,divisor): \n",
    "            neg = (dividend < 0) != (divisor < 0)\n",
    "            dividend, divisor = abs(dividend), abs(divisor)\n",
    "            dividend_, divisor_ = dividend, divisor\n",
    "            ans, record = 0, 1\n",
    "            if dividend < divisor:\n",
    "                return 0\n",
    "            while dividend_ >= divisor_:\n",
    "                dividend_ -= divisor_\n",
    "                ans += record\n",
    "                record += record\n",
    "                divisor_ += divisor_\n",
    "            if neg:\n",
    "                ans += way2_helper(dividend_,divisor)\n",
    "                ans = -ans\n",
    "            else:\n",
    "                ans += way2_helper(dividend_,divisor)\n",
    "            return min(ans,pow(2,31)-1)\n",
    "        return way2_helper(dividend,divisor)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        isNeg = (dividend < 0) ^ (divisor < 0)\n",
    "        count = 1\n",
    "        result = 0\n",
    "        dividend = abs(dividend)\n",
    "        divisor = abs(divisor)\n",
    "        overflow = 2**31\n",
    "        while dividend >= (divisor << 1):\n",
    "            divisor <<= 1\n",
    "            count <<= 1\n",
    "        while dividend > 0 and divisor >= 1:\n",
    "            if dividend >= divisor:\n",
    "                dividend -= divisor\n",
    "                result += count\n",
    "            divisor >>=1 \n",
    "            count >>= 1\n",
    "        if isNeg:\n",
    "            if result >= overflow:\n",
    "                result = overflow\n",
    "            return result*-1\n",
    "        else:\n",
    "            if result >= overflow:\n",
    "                result = overflow - 1\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        sign = -1 if ((dividend < 0) ^ (divisor < 0)) else 1\n",
    "        m = abs(dividend)\n",
    "        n = abs(divisor)\n",
    "        res = 0\n",
    "        \n",
    "        while(m >= n):\n",
    "            temp = n\n",
    "            countleftshift = 1\n",
    "            while(m > (temp << 1)): # <<1 --> x2\n",
    "                temp <<= 1\n",
    "                countleftshift <<= 1\n",
    "            m -= temp\n",
    "            res += countleftshift\n",
    "            \n",
    "        if dividend == -(2 ** 31) and divisor == 1:\n",
    "            return dividend\n",
    "        if res < -(2 ** 31) or res > 2 ** 31 - 1:\n",
    "            return 2 ** 31 - 1\n",
    "        \n",
    "        \n",
    "        return res if sign == 1 else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math        \n",
    "class Solution:\n",
    "    def divide(self,dividend, divisor):\n",
    "        INT_MAX=math.pow(2,31)-1\n",
    "        m = abs(dividend)\n",
    "        n = abs(divisor)\n",
    "        res = 0\n",
    "        if (m < n):return 0    \n",
    "        while m >= n:\n",
    "            t = n\n",
    "            p = 1\n",
    "            while m >(t << 1):\n",
    "                t <<= 1\n",
    "                p <<= 1\n",
    "            res += p\n",
    "            m -= t\n",
    "        if (dividend < 0) ^ (divisor < 0):res = -res\n",
    "        return min(int(INT_MAX),int(res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "         \n",
    "        neg=( (dividend < 0) != (divisor < 0) )\n",
    "        dividend = left = abs(dividend)\n",
    "        divisor  = div  = abs(divisor)\n",
    "        Q = 1\n",
    "        ans = 0\n",
    "        while left >= divisor:\n",
    "            left -= div\n",
    "            ans  += Q \n",
    "            Q    += Q\n",
    "            div  += div\n",
    "            if left < div:\n",
    "                div = divisor\n",
    "                Q = 1\n",
    "        if neg:\n",
    "            return max(-ans, -2147483648)\n",
    "        else:\n",
    "            return min(ans, 2147483647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):     \n",
    "        neg=( (dividend < 0) != (divisor < 0) )\n",
    "        dividend = left = abs(dividend)\n",
    "        divisor  = div  = abs(divisor)\n",
    "        Q = 1\n",
    "        ans = 0\n",
    "        while left >= divisor:\n",
    "            left -= div\n",
    "            ans  += Q \n",
    "            Q    <<= 2\n",
    "            div  <<= 2\n",
    "            if left < div:\n",
    "                div = divisor\n",
    "                Q = 1\n",
    "        if neg:\n",
    "            return max(-ans, -2147483648)\n",
    "        else:\n",
    "            return min(ans, 2147483647)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        max_int = int(math.pow(2, 31) - 1)\n",
    "        min_int = -int(math.pow(2, 31))\n",
    "\n",
    "        flag = True\n",
    "        if divisor == 0:\n",
    "            return -1\n",
    "        if dividend == 0:\n",
    "            return 0\n",
    "        if (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0):\n",
    "            flag = False\n",
    "        divisor = abs(divisor)\n",
    "        dividend = abs(dividend)\n",
    "\n",
    "        result = 0\n",
    "        while divisor <= dividend:\n",
    "            tmp = divisor\n",
    "            r = 1\n",
    "            while tmp <= dividend:\n",
    "                tmp = tmp << 1\n",
    "                r = r << 1\n",
    "            dividend = dividend - (tmp >> 1)\n",
    "            r = r >> 1\n",
    "            result += r\n",
    "\n",
    "        if not flag:\n",
    "            result = -result\n",
    "\n",
    "        if result < min_int or result > max_int:\n",
    "            return max_int\n",
    "        else:\n",
    "            return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if dividend == -2147483648 and divisor == -1:\n",
    "            return 2147483647\n",
    "        sign = -1 if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0) else 1\n",
    "        new_dividend = abs(dividend)\n",
    "        new_divisor  = abs(divisor)\n",
    "        result = new_divisor\n",
    "        count = 0\n",
    "        times = 100000\n",
    "        gap = sum([new_divisor for i in range(times)])\n",
    "        while result <= new_dividend:\n",
    "            if result + gap > new_dividend:\n",
    "                times = 1\n",
    "                gap = new_divisor\n",
    "            result += gap\n",
    "            count += times\n",
    "        return count if sign == 1 else -count\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def simple_div(self, end, sor):\n",
    "        i, res, remainder = 0, 0, 0\n",
    "        while True:\n",
    "            i += sor\n",
    "            if i > end:\n",
    "                i -= sor\n",
    "                break\n",
    "            res += 1\n",
    "        remainder = end - i\n",
    "        return res, remainder\n",
    "\n",
    "    def divide(self, dividend, divisor):\n",
    "        \"\"\"\n",
    "        :type dividend: int\n",
    "        :type divisor: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        remainder = ''\n",
    "        result = ''\n",
    "        INT_MAX = 2 ** 31 - 1\n",
    "        INT_MIN = (-2) ** 31\n",
    "        dividend_flag = divisor_flag = result_flag = -1\n",
    "        if dividend >= 0: dividend_flag = 1\n",
    "        if divisor > 0: divisor_flag = 1\n",
    "        if dividend_flag == divisor_flag: result_flag = 1\n",
    "        dividend_str = str(abs(dividend))\n",
    "        for elem in dividend_str:\n",
    "            end = int(str(remainder) + elem)\n",
    "            res, remainder = self.simple_div(end, abs(divisor))\n",
    "            result = result + str(res)\n",
    "        result = result_flag * int(result)\n",
    "        if result > INT_MAX or result < INT_MIN: return INT_MAX\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class Solution:\n",
    "    def divide(self, divd: int, dior: int) -> int:\n",
    "        res = 0\n",
    "        sign =  1 if divd ^ dior >= 0 else -1\n",
    "        divd = abs(divd)\n",
    "        dior = abs(dior)\n",
    "        while divd >= dior:\n",
    "            res += 1\n",
    "            divd -= dior\n",
    "        res = res*sign \n",
    "        return min(max(-2**31, res), 2**31-1)\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        sign = (dividend > 0) ^ (divisor > 0)\n",
    "        dividend = abs(dividend)\n",
    "        divisor = abs(divisor)\n",
    "        count = 0\n",
    "        #把除数不断左移，直到它大于被除数\n",
    "        while dividend >= divisor:\n",
    "            count += 1\n",
    "            divisor <<= 1\n",
    "        result = 0\n",
    "        while count > 0:\n",
    "            count -= 1\n",
    "            divisor >>= 1\n",
    "            if divisor <= dividend:\n",
    "                result += 1 << count #这里的移位运算是把二进制（第count+1位上的1）转换为十进制\n",
    "                dividend -= divisor\n",
    "        if sign: \n",
    "            result = -result\n",
    "        return result if -(1<<31) <= result <= (1<<31)-1 else (1<<31)-1 \n",
    "'''\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        sig = True if dividend*divisor > 0 else False  # 判断二者相除是正or负\n",
    "        dividend, divisor= abs(dividend), abs(divisor)  # 将被除数和除数都变成正数\n",
    "        res = 0                               # 用来表示减去了多少个除数，也就是商为多少\n",
    "        while divisor <= dividend:              # 当被除数小于除数的时候终止循环\n",
    "            tmp_divisor, count = divisor, 1     # 倍增除数初始化\n",
    "            while tmp_divisor <= dividend:      # 当倍增后的除数大于被除数重新，变成最开始的除数\n",
    "                dividend -= tmp_divisor\n",
    "                res += count\n",
    "                count += 1                      # 更新除数扩大的倍数\n",
    "                tmp_divisor = divisor*count     # 更新除数\n",
    "        res_value = res if sig == True else -res  # 给结果加上符号\n",
    "        return max(min(res_value, 2**31-1), -2**31)\n",
    "'''\n",
    "class Solution:\n",
    "    def divide(self, dividend, divisor):\n",
    "        sig = True if dividend*divisor > 0 else False   # 判断二者相除是正or负\n",
    "        dividend, divisor= abs(dividend), abs(divisor)  # 将被除数和除数都变成正数\n",
    "        res = 0                                         # 用来表示减去了多少个除数，也就是商为多少\n",
    "        while divisor <= dividend:                      # 当被除数小于除数的时候终止循环\n",
    "            tmp_divisor, count = divisor, 1             # 倍增除数初始化\n",
    "            while tmp_divisor <= dividend:              # 当倍增后的除数大于被除数重新，变成最开始的除数\n",
    "                dividend -= tmp_divisor\n",
    "                res += count\n",
    "                count <<= 1                             # 向左移动一位\n",
    "                tmp_divisor <<= 1                       # 更新除数(将除数扩大两倍)\n",
    "        res_value = res if sig == True else -res        # 给结果加上符号\n",
    "        return max(min(res_value, 2**31-1), -2**31)\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dev(self,a,b):\n",
    "        if a < b :\n",
    "            return 0\n",
    "        count = 1\n",
    "        tb = b\n",
    "        while (tb + tb) <= a:\n",
    "            count = count + count\n",
    "            tb = tb + tb\n",
    "        return count + self.dev(a-tb,b)\n",
    "\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if dividend == divisor :\n",
    "            return 1\n",
    "        if divisor == 1:\n",
    "            return dividend\n",
    "        # 是否为正数\n",
    "        flag = False\n",
    "        if (dividend > 0 and divisor <0) or (dividend < 0 and divisor > 0) :\n",
    "            flag = True\n",
    "        a = abs(dividend)\n",
    "        b = abs(divisor)\n",
    "        res = self.dev(a,b)\n",
    "        if res > 2147483647 :\n",
    "            res = 2147483647\n",
    "        if flag :\n",
    "            return -res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if (dividend < -2**31) or (dividend > 2**31-1):\n",
    "            return None\n",
    "        if (divisor < -2**31) or (divisor > 2**31-1):\n",
    "            return None\n",
    "\n",
    "        flag = False\n",
    "        if dividend > 0 and divisor > 0:\n",
    "            pass\n",
    "        elif dividend > 0 and divisor < 0:\n",
    "            divisor = -divisor\n",
    "            flag = True\n",
    "        elif dividend < 0 and divisor > 0:\n",
    "            dividend = -dividend\n",
    "            flag = True\n",
    "        else:\n",
    "            dividend = -dividend\n",
    "            divisor = -divisor\n",
    "\n",
    "        if dividend == 0 or dividend < divisor:\n",
    "            return 0\n",
    "        if dividend == divisor:\n",
    "            if flag:\n",
    "                return -1\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        i = 1\n",
    "        temp = divisor\n",
    "        while divisor < dividend:\n",
    "            last_divisor = divisor\n",
    "            divisor += divisor\n",
    "            last_i = i\n",
    "            i += i\n",
    "        divisor -= last_divisor\n",
    "        i -= last_i\n",
    "        i += self.divide(dividend-divisor, temp)\n",
    "        if flag:\n",
    "            if -i >= 2**31-1:\n",
    "                return 2**31-1\n",
    "            return -i\n",
    "        else:\n",
    "            if i >= 2**31-1:\n",
    "                return 2**31-1\n",
    "            return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exponents(self, dividend, divisor):\n",
    "        dr_mask = divisor\n",
    "        n = 0\n",
    "        dif = dividend\n",
    "        if(dividend<dr_mask):\n",
    "            return 0,dif,True,False\n",
    "        else:\n",
    "            while(dividend>=dr_mask):\n",
    "                dif = dividend-dr_mask\n",
    "                dr_mask = dr_mask+dr_mask\n",
    "                if(n>30):return 0,dif,True,True\n",
    "                n = n+1\n",
    "                if dif<divisor:\n",
    "                    return 2**(n-1),dif,True,False\n",
    "        return 2**(n-1),dif,False,False\n",
    "    \n",
    "    \n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if (dividend>divisor):\n",
    "            if (divisor>0):\n",
    "                Boo = False\n",
    "                Boo2 = False\n",
    "                r = 0\n",
    "                dif = dividend\n",
    "                while (not Boo):\n",
    "                    n,dif,Boo,Boo2 = self.exponents(dif,divisor)\n",
    "                    if(Boo2):return 2**31-1\n",
    "                    #print(n)\n",
    "                    r = r+n\n",
    "                return r\n",
    "            else:\n",
    "                Boo = False\n",
    "                Boo2 = False\n",
    "                r = 0\n",
    "                dif = dividend\n",
    "                while (not Boo):\n",
    "                    n,dif,Boo,Boo2 = self.exponents(dif,-divisor)\n",
    "                    if(Boo2):return -2**31\n",
    "                    r = r+n\n",
    "                return -r\n",
    "        else:\n",
    "            if (divisor>0):\n",
    "                Boo = False\n",
    "                Boo2 = False\n",
    "                r = 0\n",
    "                if(dividend>0):\n",
    "                    dif = dividend\n",
    "                else:\n",
    "                    dif = -dividend\n",
    "                while (not Boo):\n",
    "                    n,dif,Boo,Boo2 = self.exponents(dif,divisor)\n",
    "                    if(Boo2):return -2**31\n",
    "                    r = r+n\n",
    "                if dividend<0:\n",
    "                    r = -r\n",
    "                return r\n",
    "            else:\n",
    "                Boo = False\n",
    "                Boo2 = False\n",
    "                r = 0\n",
    "                dif = -dividend\n",
    "                while (not Boo):\n",
    "                    n,dif,Boo,Boo2 = self.exponents(dif,-divisor)\n",
    "                    if(Boo2):return 2**31-1\n",
    "                    r = r+n\n",
    "                return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        n = 30\n",
    "        dd = [1]\n",
    "        xx = [divisor]\n",
    "        for i in range(n):\n",
    "            dd.append(dd[-1]+dd[-1])\n",
    "            xx.append(xx[-1]+xx[-1])\n",
    "        count = 0\n",
    "        for i in range(n-1,-1,-1):\n",
    "            d = dd[i]\n",
    "            divisor_tmp = xx[i]\n",
    "            dividend_abs = dividend if dividend >= 0 else -dividend\n",
    "            divisor_abs = divisor_tmp if divisor_tmp >= 0 else -divisor_tmp\n",
    "            if dividend_abs < divisor_abs:\n",
    "                continue\n",
    "            while dividend_abs >= divisor_abs:\n",
    "                if dividend < 0 and divisor < 0 or dividend > 0 and divisor > 0:\n",
    "                    dividend = dividend-divisor_tmp\n",
    "                    count += d\n",
    "                else:\n",
    "                    dividend = dividend+divisor_tmp\n",
    "                    count -= d\n",
    "                dividend_abs = dividend if dividend >= 0 else -dividend\n",
    "        if count > pow(2,31) -1 or count < -pow(2,31): count = pow(2,31)-1    \n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        flag = 1\n",
    "        if dividend < 0: flag *= -1\n",
    "        if divisor < 0: flag *= -1\n",
    "\n",
    "        res = abs(dividend) // abs(divisor)\n",
    "        res *= flag\n",
    "\n",
    "        if res < -2 ** 31 or res > 2 ** 31 - 1:\n",
    "            return 2 ** 31 - 1\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        result = 0\n",
    "        flag = 1\n",
    "        if dividend ^ divisor < 0: flag = -1\n",
    "        dividend = abs(dividend)\n",
    "        divisor = abs(divisor)\n",
    "        while dividend >= divisor:\n",
    "            tmp, i = divisor, 1\n",
    "            while dividend >= tmp:\n",
    "                dividend -= tmp\n",
    "                result += i\n",
    "                i <<= 1\n",
    "                tmp <<= 1\n",
    "        result = result * flag\n",
    "        return min(max(-2 ** 31, result), 2 ** 31 - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        def search(a, b):\n",
    "            if a < b:\n",
    "                return 0\n",
    "            result = 1\n",
    "            cur = b\n",
    "            while cur + cur < a:\n",
    "                cur += cur\n",
    "                result = result + result\n",
    "            return result + search(a-cur, b)\n",
    "        if (divisor > 0 and dividend > 0) or (divisor < 0 and dividend < 0):\n",
    "            if abs(divisor) > abs(dividend):\n",
    "                return 0\n",
    "            flag = 0\n",
    "        else:\n",
    "            flag = 1\n",
    "        if divisor == 1:\n",
    "            if dividend > 2**31 - 1:\n",
    "                return 2**31 - 1\n",
    "            elif dividend < -2**31:\n",
    "                return -2**31\n",
    "            return dividend\n",
    "        if divisor == -1:\n",
    "            if dividend >= 2**31:\n",
    "                return -2**31\n",
    "            elif dividend <= -2**31 + 1:\n",
    "                return 2**31 - 1\n",
    "            return -dividend\n",
    "        dividend = abs(dividend)\n",
    "        divisor = abs(divisor)\n",
    "        result = search(dividend, divisor)\n",
    "        if flag == 0 and result >= 2**31 - 1:\n",
    "            return 2**31 - 1\n",
    "        elif flag == 1 and -result <= -2**31:\n",
    "            return -2**31\n",
    "        if flag == 0:\n",
    "            return result\n",
    "        else:\n",
    "            return -result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        MIN_INT, MAX_INT = -2147483648, 2147483647\n",
    "        sign = 1\n",
    "        if dividend < 0:\n",
    "            sign *= -1\n",
    "            dividend *= -1\n",
    "        if divisor < 0:\n",
    "            sign *= -1\n",
    "            divisor *= -1\n",
    "        \n",
    "        def solver(dividend,divisor):\n",
    "            if dividend < divisor:\n",
    "                return 0\n",
    "            cur = divisor\n",
    "            multiple = 1\n",
    "            while cur + cur < dividend:\n",
    "                cur += cur\n",
    "                multiple += multiple\n",
    "            return multiple + solver(dividend-cur,divisor)\n",
    "        \n",
    "        quotient = solver(dividend,divisor)\n",
    "        quotient *= sign\n",
    "        if quotient > MAX_INT:\n",
    "            return MAX_INT\n",
    "        elif quotient < MIN_INT:\n",
    "            return MIN_INT\n",
    "        else:\n",
    "            return quotient\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        def recursion(dividend: int, divisor: int):\n",
    "            i, a, b = 0, abs(dividend), abs(divisor)\n",
    "            print(a,b)\n",
    "            if a == 0 or a < b:\n",
    "                return 0\n",
    "            while b <= a:\n",
    "                b <<= 1\n",
    "                i += 1\n",
    "            res = (1<<(i-1)) + recursion(a-(b>>1), abs(divisor))\n",
    "            if (dividend ^ divisor) < 0:\n",
    "                res = -res\n",
    "            return min(res, (1<<31)-1)\n",
    "        \n",
    "        return recursion(dividend, divisor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        MIN_INT, MAX_INT = -2147483648, 2147483647\n",
    "        if dividend == 0:\n",
    "            return 0\n",
    "        if divisor == 1:\n",
    "            return dividend\n",
    "        if divisor == -1:\n",
    "            if dividend == MIN_INT:\n",
    "                return MAX_INT\n",
    "            return 0-dividend\n",
    "        p = 0\n",
    "        if (divisor > 0 and dividend < 0) or (divisor < 0 and dividend > 0):\n",
    "            p = 1\n",
    "        dividend = abs(dividend)\n",
    "        divisor = abs(divisor)\n",
    "        self.n = 0\n",
    "        self.di = divisor\n",
    "        def dd(dividend, divisor, k):\n",
    "\n",
    "            if dividend < self.di:\n",
    "                return\n",
    "            if divisor == dividend:\n",
    "                self.n += k\n",
    "\n",
    "                return\n",
    "            if divisor > dividend:\n",
    "                self.n += k>>1\n",
    "\n",
    "                dd(dividend - (divisor >> 1), self.di, 1)\n",
    "            else:\n",
    "                dd(dividend, divisor << 1, k << 1)\n",
    "        dd(dividend, divisor, 1)\n",
    "        if p == 1:\n",
    "            self.n = -self.n\n",
    "        return self.n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if dividend==-2147483648 and divisor==-1:\n",
    "            return 2147483647\n",
    "        return int(dividend/divisor)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bindary_search(self,a,b) :\n",
    "        l,r=0,32\n",
    "        ret = -1\n",
    "        while l<=r :\n",
    "            mid=(l+r)>>1\n",
    "            if a-(b<<mid) <0 :\n",
    "                r=mid-1\n",
    "            elif a-(b<<mid) >0 :\n",
    "                ret=mid\n",
    "                l=mid+1\n",
    "            else : return mid\n",
    "        return ret\n",
    "\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        sign=1\n",
    "        if divisor<0 :\n",
    "            sign=-sign\n",
    "            divisor=-divisor\n",
    "        if dividend<0 :\n",
    "            sign=-sign\n",
    "            dividend=-dividend\n",
    "        ans=0\n",
    "        while dividend>=divisor :\n",
    "            i=self.bindary_search(dividend,divisor)\n",
    "            if i==-1 :\n",
    "                print(ans)\n",
    "                break\n",
    "            else :\n",
    "                ans|=(1<<i)\n",
    "                dividend-=(divisor<<i)\n",
    "        if sign==-1 :\n",
    "            ans=-ans\n",
    "        if ans>2147483647:\n",
    "            return 2147483647\n",
    "        elif ans<-2147483648 :\n",
    "            return -2147483648\n",
    "        else :\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if divisor == 1:\n",
    "            return dividend\n",
    "        if divisor == -1:\n",
    "            return 2147483647 if dividend==-2147483648 else -dividend\n",
    "        ans = dividend // divisor\n",
    "        if dividend % divisor == 0:\n",
    "            return ans\n",
    "        if ans < 0:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if dividend==-2147483648 and divisor==-1:\n",
    "            return 2147483647\n",
    "        sign = (divisor*dividend == abs(divisor*dividend))\n",
    "        dividend=abs(dividend)\n",
    "        divisor=abs(divisor)\n",
    "\n",
    "        lst = {}\n",
    "        factor=divisor\n",
    "        cnt = 1\n",
    "        while factor<=dividend:\n",
    "            lst[cnt] = factor\n",
    "            factor+=factor\n",
    "            cnt+=cnt\n",
    "\n",
    "        cnt>>=1\n",
    "        res = 0\n",
    "        while cnt>0:\n",
    "            if lst[cnt]<=dividend:\n",
    "               res+=cnt\n",
    "               dividend-=lst[cnt]\n",
    "            cnt>>=1\n",
    "\n",
    "        if not sign:\n",
    "            res*=-1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        def quickMul(N, divisor):\n",
    "            if N < divisor:\n",
    "                return 0\n",
    "            elif N == divisor:\n",
    "                return 1\n",
    "            counter, curr_val = 1, divisor\n",
    "            last_counter, last_val = None, None \n",
    "\n",
    "            \n",
    "            while curr_val < N:\n",
    "                last_counter, last_val = counter, curr_val\n",
    "                curr_val  += curr_val                \n",
    "                counter += counter\n",
    "\n",
    "            '''\n",
    "            这个while循环是为了找出不超过dividend情况下翻了几倍\n",
    "            e.g.\n",
    "            dividend = 10, divisor = 3\n",
    "            initVal: curr_val = 3, N = 10\n",
    "\n",
    "            i=0:\n",
    "            last_counter, last_val = 1, 3\n",
    "            curr_val = 6 counter = 2\n",
    "\n",
    "            i=1:\n",
    "            last_counter, last_val = 2, 6 \n",
    "            curr_val = 12 counter = 4 \n",
    "\n",
    "            i=2:\n",
    "            curr_val > 10 退出循环\n",
    "            此时\n",
    "            last_counter, last_val = 2, 6 \n",
    "\n",
    "            再看下边的return\n",
    "            last_counter 是当前最大的倍数\n",
    "            quickMul(N-last_val, divisor) 是余数最大的倍数\n",
    "\n",
    "            还是上面的例子\n",
    "            last_counter, last_val = 2, 6 \n",
    "            \n",
    "            return 2 + quickMul(4, 3) \n",
    "            quickMul(4,3) = 1 + quickMul(1,3)\n",
    "            quickMul(1,3) = 0 根据边界条件\n",
    "\n",
    "            所以\n",
    "            return 2 + 1 + 0 = 3\n",
    "            '''\n",
    "\n",
    "            return last_counter + quickMul(N-last_val, divisor)\n",
    "\n",
    "        signcount = int(dividend < 0) + int(divisor < 0) #正负号\n",
    "        res = quickMul(abs(dividend), abs(divisor)) \n",
    "        if signcount == 1 and res > 2**31:res = 2**31\n",
    "        if signcount != 1 and res > 2**31-1: res = 2**31-1\n",
    "\n",
    "        return -res if signcount == 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        d1 = abs(dividend)\n",
    "        d2 = abs(divisor)\n",
    "        re = self.continue_divide(d1,d2,d2)\n",
    "        # while d1 >= d2:\n",
    "        #     re += 1\n",
    "        #     d1 -= d2\n",
    "\n",
    "        if (dividend > 0 and divisor > 0) or (dividend<0 and divisor<0):\n",
    "            if re>2147483647:\n",
    "                return 2147483647\n",
    "            return re\n",
    "        else:\n",
    "            if re< -2147483648:\n",
    "                return -2147483648\n",
    "            return -re\n",
    "    \n",
    "    def continue_divide(self, dividend: int, divisor: int, base_divide, base=1) -> int:\n",
    "        print(dividend, divisor)\n",
    "        if dividend >= divisor:\n",
    "            return base + self.continue_divide(dividend-divisor, divisor+divisor, base_divide, base+base)\n",
    "        else:\n",
    "            if divisor == base_divide:\n",
    "                return 0\n",
    "            return self.continue_divide(dividend, base_divide, base_divide)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        # 处理特殊情况\n",
    "        if dividend == 0:\n",
    "            return 0\n",
    "        if divisor == 1:\n",
    "            return dividend\n",
    "        if divisor == -1:\n",
    "            if dividend == -2**31:\n",
    "                return 2**31 - 1\n",
    "            else:\n",
    "                return -dividend\n",
    "        \n",
    "        # 确定结果的正负号\n",
    "        negative = (dividend < 0) ^ (divisor < 0)\n",
    "        \n",
    "        # 将被除数和除数都转为正数进行计算\n",
    "        dividend = abs(dividend)\n",
    "        divisor = abs(divisor)\n",
    "        \n",
    "        result = 0\n",
    "        while dividend >= divisor:\n",
    "            # 逐步减去除数，计算商的值\n",
    "            temp = divisor\n",
    "            quotient = 1\n",
    "            while dividend >= (temp << 1):\n",
    "                temp <<= 1\n",
    "                quotient <<= 1\n",
    "            dividend -= temp\n",
    "            result += quotient\n",
    "        \n",
    "        # 根据结果的正负号返回最终值\n",
    "        return -result if negative else result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        if dividend == -2147483648 and divisor == -1:\n",
    "            return 2147483647\n",
    "        a, b, res = abs(dividend), abs(divisor), 0\n",
    "        for i in range(31, -1, -1):\n",
    "            if (b << i) <= a:\n",
    "                res += 1 << i\n",
    "                a -= b << i\n",
    "        return res if (dividend > 0) == (divisor > 0) else -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def divide(self, dividend: int, divisor: int) -> int:\n",
    "        same = True\n",
    "        if (dividend > 0 and divisor < 0) or (dividend < 0 and divisor > 0):\n",
    "            same = False\n",
    "        dividend, divisor = abs(dividend), abs(divisor)\n",
    "\n",
    "        times = []\n",
    "        x = divisor\n",
    "        while x <= dividend:\n",
    "            times.append(x)\n",
    "            x += x\n",
    "        times.reverse()\n",
    "\n",
    "        ans = 0\n",
    "        for i, it in enumerate(times):\n",
    "            if it <= dividend:\n",
    "                ans += ans + 1\n",
    "                dividend -= it\n",
    "            else:\n",
    "                ans += ans\n",
    "        \n",
    "        ans = ans if same else -ans\n",
    "        if ans < -2**31:\n",
    "            return -2**31\n",
    "        elif ans > 2**31-1:\n",
    "            return 2**31-1\n",
    "        else:\n",
    "            return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
